#include <stdio.h>
#include <stdlib.h>

typedef struct BSTreeNode {
	int value;
	struct BSTreeNode * left;
	struct BSTreeNode * right;
} BSTreeNode;


BSTreeNode * BSTree2DList(BSTreeNode *&head, BSTreeNode *&tail, BSTreeNode * root) {
	if (root == NULL) {
		head = tail = NULL;
		return NULL;
	}

	BSTreeNode *l = NULL, *r = NULL;
	if (root->left) {
		BSTree2DList(head, l, root->left);
		l->right = root;
		root->left = l;
	} else {
		head = root;
	}

	if (root->right) {
		BSTree2DList(r, tail, root->right);
		r->left = root;
		root->right = r;
	} else {
		tail = root;
	}
}


int main() {
	BSTreeNode * nodes = (BSTreeNode *)malloc(sizeof(BSTreeNode)*8);
	nodes[1].value = 10;
	nodes[2].value = 6;
	nodes[3].value = 14;
	nodes[4].value = 4;
	nodes[5].value = 8;
	nodes[6].value = 12;
	nodes[7].value = 16;

	nodes[1].left = &nodes[2];
	nodes[1].right = &nodes[3];
	nodes[2].left = &nodes[4];
	nodes[2].right = &nodes[5];
	nodes[3].left = &nodes[6];
	nodes[3].right = &nodes[7];

	BSTreeNode *head = NULL, *tail = NULL;
	BSTree2DList(head, tail, &nodes[1]);

	for(BSTreeNode * s = head; s != tail; s = s->right)
		printf("%d ", s->value);
	
	printf("%d\n", tail->value);
	
	for(BSTreeNode * s = tail; s != head; s = s->left)
		printf("%d ", s->value);
	printf("%d\n", head->value);

	free(nodes);
	return 0;
}
